package demo.DataStrucAndAlgo.Tree;

import java.util.Scanner;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/31-07-31-12:01
 * @Description：demo.DataStrucAndAlgo.Tree  二叉树
 */
/*
满二叉树：
    二叉树的所有叶子结点都在最后一层，且结点总数=2^n-1,n为层数
完全二叉树：
    如果该二叉树的所有叶子结点都在最后一层或者倒数第二层，
    而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续
二叉树遍历：
    前序遍历：先输出父节点，再遍历左子树和右子树
    中序遍历：先遍历左子树，再输出父节点，再遍历右子树
    后序遍历：先遍历左子树和右子树，最后输出父节点
 */
/*
    二叉树简单结点删除
        删除根节点：重置二叉树
        删除叶子结点，即将叶子结点置空
        删除非叶子结点：将该结点之下的所有结点一并删除
*/
class Node{
    private int id;
    private int data;
    private Node left;
    private Node right;

    public Node(int id, int data) {
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", data='" + data + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder(){
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    public Node(int data) {
        this.data = data;
    }

    //后序遍历
    public void postOrder(){
        if(this.left != null){
            this.left.postOrder();
        }
        if(this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //删除结点
    public void delete(int id){
        if(this.left != null && this.left.getId() == id){   //删除左结点
            this.left = null;
            return;
        }
        if(this.right != null && this.right.getId() == id){    //删除右节点
            this.right = null;
            return;
        }
        if(this.left!=null){
            this.left.delete(id);
        }
        if(this.right != null){
            this.right.delete(id);
        }
    }
}
class binaryTree{
    private Node root;     //根节点
    public Node getRoot() {
        return root;
    }
    public void setRoot(Node root) {
        this.root = root;
    }
    //前序遍历
    public void preOrder(){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("此二叉树为空！");
        }
    }
    //中序遍历
    public void infixOrder(){
        if(root != null){
            root.infixOrder();
        }else{
            System.out.println("此二叉树为空！");
        }
    }
    //后序遍历
    public void postOrder(){
        if(root != null){
            root.postOrder();
        }else{
            System.out.println("此二叉树为空！");
        }
    }
    public void delete(int id){
        if(root == null){
            System.out.println("此二叉树为空，操作失败！");
        }else if(root.getId() == id){
            root = null;
        }else{
            root.delete(id);
        }
    }
}
public class Binary_Tree {
    public static void main(String[] args) {
        binaryTree tree=new binaryTree();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[][] temp = new int[n][3];
        Node[] node = new Node[n];
        Node node1=new Node(1,sc.nextInt());
        tree.setRoot(node1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            node1.setLeft(new Node(temp[i][1]));
            node1.setRight(new Node(temp[i][2]));
        }

//        Node node2=new Node(2,"two");
//        Node node3=new Node(3,"three");
//        Node node4=new Node(4,"four");
//        Node node5=new Node(5,"five");
//        tree.getRoot().setLeft(node2);
//        tree.getRoot().setRight(node3);
//        node3.setLeft(node4);
//        node3.setRight(node5);
//
//        System.out.println("前序遍历");
//        tree.preOrder();//1,2,3,4,5
//
//        System.out.println("中序遍历");
//        tree.infixOrder();//2,1,4,3,5
//
//        System.out.println("后序遍历");
//        tree.postOrder();//2,4,5,3,1
//
//        System.out.println("------------简单删除----------------");
//        tree.delete(3);
//        tree.infixOrder();
    }
}
